class Solution {
public:
    int numberOfSubstrings(string s) {
        vector<int> pos0={-1}; //dummy
        int total1=0; //[0, r]中1的个数
        int ans=0;
        for(int r=0; r<s.size(); r++) { //枚举字串右端点
            if(s[r]=='0') pos0.push_back(r);
            else total1++, ans+=r-pos0.back(); //单独计算不含0的子串个数   

            //倒着遍历pos0, 那么cnt0=m-i
            for(int m=pos0.size(), i=m-1; i>0&&(m-i)*(m-i)<=total1; i--) {
                int p=pos0[i-1], q=pos0[i];
                int cnt0=m-i, cnt1=r-q+1-cnt0; //[q, r]中1的个数=[q,r]的长度-cnt0
                ans+=max(q-max(cnt0*cnt0-cnt1, 0)-p, 0);
            }
        }
        return ans;
    } 
};